Đẳng thức sau

2 a b − 1 = ( 2 a − 1 ) ⋅ ( 1 + 2 a + 2 2 a + 2 3 a + ⋯ + 2 ( b − 1 ) a ) {\displaystyle 2^{ab}-1=(2^{a}-1)\cdot \left(1+2^{a}+2^{2a}+2^{3a}+\dots +2^{(b-1)a}\right)}

cho biết rằng Mn có thể là số nguyên tố chỉ nếu chính n là số nguyên tố, điều đó làm giản lược bớt việc tìm các số nguyên tố Mersenne. Mệnh đề đảo, nói rằng Mn là số nguyên tố nếu n là số nguyên tố là sai. Số nhỏ nhất cho ví dụ này là 211-1 = 23×89, là hợp số.

Đã có một số thuật toán tối ưu hóa để tìm số nguyên tố Mersenne, do đó hiện nay người ta đã biết các số nguyên tố Mersenne rất lớn.

Bốn số nguyên tố Mersenne đầu tiên M 2 = 3 {\displaystyle M_{2}=3} , M 3 = 7 {\displaystyle M_{3}=7} , M 5 = 31 {\displaystyle M_{5}=31} và M 7 = 127 {\displaystyle M_{7}=127} đã được biết từ cổ xưa. Số thứ năm, M 13 = 8191 {\displaystyle M_{13}=8191} , được tìm thấy vào trước năm 1461; hai số tiếp theo ( M 17 {\displaystyle M_{17}} và M 19 {\displaystyle M_{19}} ) tìm thấy bởi Cataldi vào năm 1588, đồng thời ông còn dự đoán cho các số mũ 23 (đã bị Fermat bác bỏ), 29 (đã bị Fermat bác bỏ), 37(đã bị Euler bác bỏ). Sau hơn một thế kỷ M 31 {\displaystyle M_{31}} được kiểm tra bởi Euler vào năm 1750 bằng Lý thuyết chỉ số. Số tiếp theo (trong lịch sử, không theo thứ tự số) là M 127 {\displaystyle M_{127}} , do Lucas tìm thấy vào năm 1876, sau đó M 61 {\displaystyle M_{61}} do Pervushin tìm vào năm 1883. Hai số nữa ( M 89 {\displaystyle M_{89}} và M 107 {\displaystyle M_{107}} ) được tìm thấy vào thế kỷ XX, bởi Powers vào năm 1911 và 1914.

Từ thế kỷ XVII, các số này được mang tên nhà toán học Pháp Marin Mersenne, người đã chứng minh và dự đoán một loạt các số nguyên tố Mersenne với các số mũ: 2, 3, 5, 7, 13, 17, 31, 67, 127, 257. Danh sách của ông đã mắc một số sai lầm, như bao gồm cả M67 (được Kohler chứng minh là hợp số vào năm 1901, cụ thể: 2 67 − 1 = 193.707.721 × 761.838.257.287 {\displaystyle 2^{67}-1=193.707.721\times 761.838.257.287} ), M257 (được chứng minh là hợp số vào năm 1952), và bị bỏ quên M61, M89 và M107.

Phương pháp tốt nhất để kiểm tra tính nguyên tố của các số Mersenne được dựa vào sự tính toán một dãy tuần hoàn, được phát biểu đầu tiên bởi Lucas năm 1878 và chứng minh bởi Lehmer vào những năm 1930. Hiện nay nó được gọi là kiểm tra Lucas-Lehmer với số Mersenne. Đặc biệt, ta có thể chứng minh rằng (với n > 2 {\displaystyle n>2} ) M n = 2 n − 1 {\displaystyle M_{n}=2^{n}-1} là số nguyên tố nếu và chỉ nếu Mn chia hết cho Sn-2, trong đó S 0 = 4 {\displaystyle S_{0}=4} và với k > 0 {\displaystyle k>0} , S k = S k − 1 2 − 2 {\displaystyle S_{k}=S_{k-1}^{2}-2} .

Đồ thị biểu diễn số các chữ số của số nguyên tố Mersenne lớn nhất đã biết theo từng năm của kỷ nguyên điện tử. Chú ý rằng trục tung độ đã được logarit hóa.

Việc tìm các số nguyên tố Mersenne thực sự được cách mạng bởi các máy tính điện tử số. Thành công đầu tiên của tư tưởng này thuộc về số nguyên tố Mersenne, M521, nhờ nỗ lực khéo léo vào lúc 10:00 P.M. ngày 30-1, 1952 khi sử dụng máy tính tự động Western U.S. National Bureau of Standards (SWAC) tại Institute for Numerical Analysis thuộc Đại học California tại Los Angeles, dưới sự điều khiển trực tiếp của Lehmer, sử dụng chương trình viết và chạy bởi GS R.M. Robinson. Nó là số nguyên tố Mersenne đầu tiên tìm thấy sau 38 năm; số tiếp theo, M607, đã được tìm thấy do computer này sau gần hai giờ chạy máy. Ba số tiếp theo  — M1279, M2203, M2281 — đã được tìm thấy với cùng chương trình trên sau nhiều tháng nữa. M4253 là số nguyên tố Mersenne đầu tiên là số nguyên tố siêu lớn (trên 1000 chữ số thập phân - titanic), và M44497 là số nguyên tố đẩu tiên có trên 10.000 chữ số thập phân (gigantic).

Đến tháng 9 năm 2008, chỉ mới biết 46 số nguyên tố Mersenne; số lớn nhất đã biết là số (243 112 609 − 1). Cũng như nhiều số nguyên tố Mersenne trước đó, nó được tìm ra nhờ dự án tính toán phân tán trên Internet, được biết với tên gọi Tìm kiếm số nguyên tố Mersenne khổng lồ trên Internet (Great Internet Mersenne Prime Search - GIMPS).